/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***二分查找         P78                       ***/
/***C++ 实现版本    written by Daniel           ***/

/* 查找的序列必须是有序数列，时间复杂度为O(log 2 N)*/
/*课后题，查找多个相同的数据*/
#include <iostream>

using std::cout;
using std::endl;

void binaryFind(int *arr, int size, int left, int right, int value, int *index)
{
    int mid = (left + right) / 2;
    cout << "mid=" << mid << endl;
    if (left > right)
    {
        *index = -1;
        return;
    }

    if (arr[mid] > value)
    {
        binaryFind(arr, size, left, mid - 1, value, index);
        //cout << "left=" << left << "mid-1=" << mid - 1 << endl;
    }
    else if (arr[mid] < value)
    {
        binaryFind(arr, size, mid + 1, right, value, index);
        //cout << "mid+1=" << left << "right=" << right << endl;
    }
    else
    {
        *index = mid;
        return;
    }
}

int main(int argc, char **argv)
{
    int array[11] = {1, 8, 10, 89, 563,768,893,999,1000, 1234,2000};
    int index = 0;
    binaryFind(array, 11, 0, 11, 768, &index);
    if (index == -1)
    {
        cout << "集合中没有该元素" << endl;
    }
    else
    {
        cout << "该元素的下标为" << index << endl;
    }
}